
#include <vector>
#include <assert.h>
#include <iostream>
#include "bitset模拟.hpp"
#include "Common.h"


using namespace std;
template<class K, size_t N = 100, class KToD1 = K2D1
        , class KToD2 = K2D2
        , class KToD3 = K2D3
        , class KToD4 = K2D4
        , class KToD5 = K2D5>
class BloomFilter{
public:
    BloomFilter()
    :_bst(),
    _size(0)
    {}
    bool Insert(const K& key){
        std::size_t  totalBits=_bst.size();
        size_t hashAddr=KToD1()(key)%totalBits;
        _bst.set(hashAddr);

        totalBits=_bst.size();
         hashAddr=KToD2()(key)%totalBits;
        _bst.set(hashAddr);

        totalBits=_bst.size();
         hashAddr=KToD3()(key)%totalBits;
        _bst.set(hashAddr);

        totalBits=_bst.size();
        hashAddr=KToD4()(key)%totalBits;
        _bst.set(hashAddr);

        totalBits=_bst.size();
        hashAddr=KToD5()(key)%totalBits;
        _bst.set(hashAddr);

        _size++;

        return true;
    }
    bool  find(const K& key){
        size_t totalBits = _bst.size();
        size_t hashAddr = KToD1()(key) % totalBits;
        cout << key << ":" << hashAddr << " ";
        if (!_bst.test(hashAddr))
            return false;

        hashAddr = KToD2()(key) % totalBits;
        cout << hashAddr << " ";
        if (!_bst.test(hashAddr))
            return false;

        hashAddr = KToD3()(key) % totalBits;
        cout << hashAddr << " ";
        if (!_bst.test(hashAddr))
            return false;

        hashAddr = KToD4()(key) % totalBits;
        cout << hashAddr << " ";
        if (!_bst.test(hashAddr))
            return false;

        hashAddr = KToD5()(key) % totalBits;
        cout << hashAddr << " ";
        if (!_bst.test(hashAddr))
            return false;
        cout << endl;

        // 注意：虽然返回的是true
        // 但是key是可能存在，只不过误差的概率比较小
        return true;
    }
    std::size_t  size(){
        return _size;
    }
private:
    bitset1<N*5>_bst;
    std::size_t  _size;
};
int main(){

    BloomFilter<std::string> bf;

    bf.Insert("欧阳锋");
    bf.Insert("欧阳克");
    bf.Insert("孙晓果");
    bf.Insert("金轮法王");
    bf.Insert("桑吉");
    bf.Insert("abc");

    if (bf.find("过儿"))
    {
        cout << "坏人" << endl;
    }
    else
    {
        cout << "好人" << endl;
    }

    if (bf.find("欧阳锋"))
    {
        cout << "坏人" << endl;
    }
    else
    {
        cout << "好人" << endl;
    }

    if (bf.find("bca"))
    {
        cout << "坏人" << endl;
    }
    else
    {
        cout << "好人" << endl;
    }
    return 0;
}
